package tree

//给你二叉树的根节点root 和一个表示目标和的整数targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和targetSum 。
//
//叶子节点 是指没有子节点的节点。

//方法1：递归
//假定从根节点到当前节点的值之和为 val，我们可以将这个大问题转化为一个小问题：是否存在从当前节点的子节点到叶子的路径，满足其路径和为 sum - val。
//时间复杂度：O(N)，其中 NN 是树的节点数。对每个节点访问一次。
//
//空间复杂度：O(H)，其中 HH 是树的高度。空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为 O(N)O(N)。平均情况下树的高度与节点数的对数正相关，空间复杂度为 O(\log N)O(logN)。
//

func HasPathSumDFS(root *Node, sum int) bool {
	if root == nil {
		return false
	}
	//判断叶子节点
	if root.Left == nil && root.Right == nil {
		return sum == root.Val
	}
	return HasPathSumDFS(root.Left, sum-root.Val) || HasPathSumDFS(root.Right, sum-root.Val)
}

//广度优先搜索
//这样我们使用两个队列，分别存储将要遍历的节点，以及根节点到这些节点的路径和即可
//时间复杂度：O(N)，其中 NN 是树的节点数。对每个节点访问一次。
//
//空间复杂度：O(N)，其中 NN 是树的节点数。空间复杂度主要取决于队列的开销，队列中的元素个数不会超过树的节点数

func HasPathSumBFS(root *Node, sum int) bool {
	if root == nil {
		return false
	}

	queNode := []*Node{}
	queVal := []int{}

	queNode = append(queNode, root)
	queVal = append(queVal, root.Val)

	for len(queNode) != 0 {
		now := queNode[0]
		queNode = queNode[1:]
		temp := queVal[0]
		queVal = queVal[1:]

		//叶子节点处判断
		if now.Left == nil && now.Right == nil {
			if temp == sum {
				return true
			}
			continue
		}

		if now.Left != nil {
			queNode = append(queNode, now.Left)
			queVal = append(queVal, now.Left.Val+temp)
		}

		if now.Right != nil {
			queNode = append(queNode, now.Right)
			queVal = append(queVal, now.Right.Val+temp)
		}
	}
	return false
}
